package com.hard;


import java.util.LinkedList;
import java.util.List;
//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
public class SolutionLCR170 {
    int[] record, tmp;

    public int reversePairs(int[] record) {
        this.record = record;
        tmp = new int[record.length];
        return mergeSort(0, record.length - 1);
    }

    private int mergeSort(int l, int r) {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int res = mergeSort(l, mid) + mergeSort(mid + 1, r);
        for (int i = l; i < r + 1; i++) {
            tmp[i] = record[i];
        }
        int i = l, j = mid + 1;
        for (int k = l; k < r + 1; k++) {
            if (i == mid + 1) {
                record[k] = tmp[j++];
            } else if (j == r + 1 || tmp[i] <= tmp[j]) {
                record[k] = tmp[i++];
            } else {
                record[k] = tmp[j++];
                res += mid - i + 1;
            }
        }
        return res;
    }
}
